1. Field of the Invention
The invention generally relates to design and layout of integrated circuits and more specifically relates to automatic placement and routing of signals on VLSI semiconductors and the software for performing such placement and routing.
2. Description of the Related Art
Routing signals (conductors) on integrated circuits from sources to destinations or between multiple drivers and receivers is vital to the design and production of integrated circuits. As the density of circuitry on an integrated circuit increases, the number of these signals tends to increase, thus making routing of the signals more complex. Additionally, the wider and widening data busses tend to result in increasing numbers of signals that must be routed to have similar delays as a group.
In semiconductors, horizontal signal legs often are routed in a first layer of conductor (metal or polysilicon for example) and vertical signal legs are often routed in a second layer of conductor. The horizontal and vertical signal legs are alternated for succeeding layers of conductors (up to the seven or eight layers that may currently be available). An alternative method of routing uses conductors that actually xe2x80x9cbendxe2x80x9d or are used for both horizontal and vertical legs of a signal.
Furthermore, a common approach to routing involves attempting a general global routing of signals across a device, resulting in assignment of signals to a path through a set of regions. Then, routing of each region of the device occurs, wherein routing of the signals within each region is subject to constraints resulting from the global routing, and signals routed through multiple regions must be routed such that there are no discontinuities at region boundaries.
FIG. 1 illustrates two of the problems commonly found when attempting to route signals on an integrated circuit. The signals enter or exit the regions at crosspoints, the points or vertices on the boundary of the region through which the signal passes. Note that these points or vertices are not geometrically ideal, they have a width fixed by the design limitations of the integrated circuit and the process by which it is manufactured. Likewise, the crosspoints require a minimum spacing that also comes from the same design limitations of the integrated circuit and the process by which it is manufactured. The integrated circuit is divided up into regions through which signals are routed, as illustrated by the grid pattern.
The first problem illustrated is an L-shaped crossover, in which two signals are routed such that portions of the two signals are routed close to each other or even overlap. Signal A is routed from terminator A1 to terminator A4. Along the route, signal A enters a first area at crosspoint A2 and leaves the first area at crosspoint A3. Signal B is routed from terminator B1 to terminator B4. Signal B is also routed through a first area, entering at crosspoint B2 and leaving at crosspoint B3. (It will be appreciated that the conventions of entering and leaving are used for ease of illustration, and that the conductors or signals allow for flow of electrons or information in any direction between terminators on the signal.) As is apparent from the illustration, terminator B4 and terminator A4 are nearly at the same location in terms of the horizontal axis of the integrated circuit. As a result, crosspoint A3 and crosspoint B3 are nearly connectable by a straight line parallel to the edge of the semiconductor, and thus signal A and signal B nearly overlap in the region where they are made up of horizontal signal legs. If these two horizontal signal legs are routed in the same conductor (for example the first metal layer of a silicon semiconductor), they will be nearly impossible to route because each separate leg within a layer must be separated by a minimum distance determined by the manufacturing process. Furthermore, even this minimum distance may be insufficient, as crosstalk between the signal legs may result in unacceptable noise on the two signal lines.
The second problem illustrated in FIG. 1 is an X overlap between two signals. Signal C is routed from terminator C1 to terminator C4. Signal C enters a second area at crosspoint C2 and leaves the second area at crosspoint C3. Signal D is routed from terminator D1 to terminator D4. Signal D also traverses the second area, entering at crosspoint D2 and leaving at crosspoint D3. As will be appreciated, terminator C1 and terminator D4 are essentially lined up on a line parallel to the edge of the semiconductor, as are terminator D1 and terminator C4. As a result, signal C and signal D must cross at some point to achieve a reasonably short routing between the terminators for each signal. An actual diagonal crossing as illustrated here is likely to result in one of the signals being nearly unroutable or actually unroutable, since it would be nearly impossible to avoid some sort of overlap. Furthermore, diagonally routed signals in a design which primarily uses horizontal or vertical signals tend to effectively foreclose large areas of the integrated circuit from use for other signals relative to the signals actually routed therein.
In one embodiment the invention is a method. The method includes finding costs to route a net to a set of crosspoints on a boundary. The method also includes propagating the costs to a succeeding set of nodes.